def matrix_multiply(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
    """
    矩阵乘法。
    """

    def rows(m: list[list[int]]) -> int:
        """
        获取矩阵行数；
        """
        return len(m)

    def columns(m: list[list[int]]) -> int:
        """
        获取矩阵列数；
        """
        return len(m[0])

    # 判断A矩阵的列和B矩阵的行是否不等；
    if columns(a) != rows(b):  # 若是；
        raise Exception("矩阵错误")

    c: list[list[int]] = [[0] * columns(b) for _ in range(rows(a))]

    for k in range(columns(b)):
        for i in range(rows(a)):
            for j in range(columns(a)):
                c[i][k] += a[i][j] * b[j][k]

    return c


def matrix_chain(p: tuple[int]):
    """
    矩阵链。
    """
    # 矩阵元素个数；
    n: int = len(p) - 1
    # 结果矩阵；
    m = [[float("inf")] * len(p) for _ in range(len(p))]
    # 标记矩阵；
    s = [[0] * len(p) for _ in range(len(p))]

    def dp(i: int, j: int):
        """
        动态规划。
        """
        if i == j:
            return 0
        for k in range(i, j):
            q = dp(i, k) + dp(k + 1, j) + p[i - 1] * p[k] * p[j]
            if q < m[i][j]:
                m[i][j] = q
                s[i][j] = k
        return m[i][j]

    dp(1, n)
    return m, s


def matrix_chain_order(p: tuple[int]):
    """
    docstring
    """
    # 矩阵元素个数；
    n: int = len(p) - 1
    # 结果矩阵生成，并对链长为1的结果统一赋值为0；
    m: list[list[float]] = [
        [float("inf") if j > i else 0 if j == i else -1 for j in range(n + 1)]
        for i in range(n + 1)
    ]

    s: list[list[int]] = [[0] * (n + 1) for _ in range(n + 1)]
    # 链长由2至n递增；
    for r in range(2, n + 1):
        # 左边界i由1至n-r+1递增；
        for i in range(1, n - r + 2):
            # 有边界j置值；
            j = i + r - 1
            # 划分k由左边界i至右边界j减1；
            for k in range(i, j):
                q: int = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
    return m, s


def print_optimal_parenthesis(s, i, j):
    """
    docstring
    """
    if i == j:
        print("A", end=" ")
    else:
        print("(", end=" ")
        print_optimal_parenthesis(s, i, s[i][j])
        print_optimal_parenthesis(s, s[i][j] + 1, j)
        print(")", end=" ")


if __name__ == "__main__":
    # 矩阵链
    p = (30, 35, 15, 5, 10, 20, 25)
    result = matrix_chain_order(p)
    print_optimal_parenthesis(result[1], 1, 6)
    # 矩阵乘法测试；
    # a = [[1, 3, 2], [4, 0, 1]]
    # b = [[1, 3], [0, 1], [5, 2]]
    # print(matrix_multiply(a, b))